//============================================================================
// Name        : qsort.cpp
// Author      : weiwei
// Version     : V1.0
// Copyright   : Your copyright notice
// Description : qsort
//============================================================================

#include<iostream>
using namespace std;

//快速排序
void qsort(int *V, int low, int high);
//分割
int partition(int *V, int low, int high);
//交换数组v中i和j位置的值
void swapVij(int *V, int i, int j);
//打印数组
void printV(const int *V, int len);

int main()
{
    int V[]= {44, 22, 2, 32, 54, 22, 88, 77, 99, 11};
    printV(V,10);

    qsort(V,0,9);
    printV(V,10);

    return 0;
}

void printV(const int *V, int len)
{
    int i =0;
    while(i<len)
    {
        cout<<*(V+i)<<"   ";
        i++;
    }
    cout<<endl;
}

void qsort(int *V, int low, int high)
{
    if(low>=high) return; // don't sort o or 1 item
    int parti = partition(V, low , high);
    if(low<parti-1)
        qsort(V, low, parti-1);
    if(parti<high)
        qsort(V,parti,high);
}

int partition(int *V, int low, int high)
{
    int pivot = *(V+(low+high)/2);
    while(low <= high)
    {
        while(*(V+low)<pivot) low ++;
        while(*(V+high)>pivot) high --;
        if(low <= high)
        {
            swapVij(V,low,high);
            low++;
            high --;
        }
    }
//    cout<<"sort"<<"" ;
//    printV(V,10);
//    cout<<endl;
    return low;
}

void swapVij(int *V, int i, int j)
{
    int temp=*(V+i);
    *(V+i)=*(V+j);
    *(V+j)=temp;
}
